• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    system and method for executing sequences on a processor. a method and system for executing a plurality of sequences are described. the method may include mapping a specified sequence priority value associated with a resting sequence to a quantized sequence priority value associated with the resting sequence if the resting sequence is ready to run. the method may further include adding the resting sequence to a ready-to-run queue and updating the quantized sequence priority value. a sequence quantum value associated with the sequence at rest can also be updated, or a combination of quantum value and quantized priority value can both be updated.
    公开号:BR112012022431B1
    申请号:R112012022431-0
    申请日:2011-02-23
    公开日:2021-08-03
    发明作者:Steven S. Thomson；Paul R. Johnson；Chirag D. Shah；Ryan C. Michel
    申请人:Qualcomm Incorporated；
    IPC主号:
    专利说明:

    Cross Reference to Related Orders
    [001] This request claims priority under U.S.C. § 119(e) of U.S. Provisional Patent Application No. 61/314,085, filed March 15, 2010. The entire contents of this provisional patent application are incorporated herein by reference.
    [002] Portable Computing Devices (PDs) are ubiquitous. These devices can include cell phones, personal digital assistants (PDAs), handheld game consoles, palmtop computers, and other handheld electronic devices. In addition to the basic function of these devices, many include peripheral functions. For example, a cell phone may include a basic function of making cell phone calls and peripheral functions of a photo camera, video camera, global positioning system (GPS) navigation, web browsing, sending and receiving emails , sending and receiving text messages, PTT capabilities, etc. As the functionality of such a device increases, the number of operating threads increases. Additionally, as the number of operating chains increases, the ability to effectively manage the execution of such chains becomes increasingly difficult.
    [003] Accordingly, what is needed is an improved system and method to run a plurality of strings on one or more processors. SUMMARY OF THE INVENTION
    [004] A method and system for performing a plurality of strings includes mapping a string-specified priority value associated with a string at rest to a string-quantized priority value associated with the string at rest if the string at rest is ready to run. This mapping includes assigning to the resting string a bucket priority value. The still string is then added to a queue that is ready to run. Then, the string-quantized priority value, a string quantum value, or a combination thereof associated with the string at rest can be updated. This update can comprise a static update using a map and a dynamic update based on a bucket priority value assigned to the chain. BRIEF DESCRIPTION OF THE DRAWINGS
    [005] In the figures, similar numerical references refer to similar parts throughout the various views unless otherwise indicated.
    [006] Figure 1 is a front plan view of a first aspect of a portable computing device (PCD) in a closed position;
    [007] Figure 2 is a front plan view of the first aspect of a PCD in an open position;
    [008] Figure 3 is a block diagram of a second aspect of a PCD;
    [009] Figure 4 is a block diagram of a processing system;
    [0010] Figure 5 is a block diagram of a prioritization system;
    [0011] Figure 6 is a flowchart illustrating a method of prioritizing a plurality of strings;
    [0012] Figure 7 is a flowchart illustrating a first aspect of a method for executing a plurality of strings;
    [0013] Figure 8 is a flowchart illustrating a static update method of a string priority quantization, a string quantum value, or a combination thereof;
    [0014] Figure 9 is a flowchart illustrating a first part of a method of dynamically updating a string priority quantization, a string quantum value, or a combination thereof;
    [0015] Figure 10 is a flowchart illustrating a second part of a method of dynamically updating a string priority quantization, a string quantum value, or a combination thereof. DETAILED DESCRIPTION OF THE INVENTION
    [0016] The term “exemplary” is used here to mean “serving as an example, case or illustration”. Any aspect described herein as "exemplary" is not necessarily to be regarded as preferred or advantageous over other aspects.
    [0017] In this description, the term "application" may also include files having executable content, such as: object code, scripts, byte code, markup language files, and patches. Additionally, an “application” referred to here may also include files that are not executable in nature, such as documents that may need to be opened or other data files that need to be accessed.
    [0018] The term "content" may also include files having executable content, such as: object code, scripts, byte code, markup language files, and patches. Additionally, “content” as referred to here may also include files that are not executable in nature, such as documents that may need to be opened or other data files that need to be accessed.
    [0019] As used in this description, the terms "component", "database", "module", "system", and the like shall refer to an entity related to computer, hardware, firmware, a combination of hardware and software , software, or running software. For example, a component can be, but is not limited to, a process running on a processor, a processor, an object, an executable element, a chain of execution, a program and/or a computer. By way of illustration, both an application running on a computing device and the computing device can be a component. One or more components can reside within a process and/or chain of execution and a component can be located on one computer and/or distributed among two or more computers. Additionally, these components can run from various computer readable media having various data structures stored on it. Components can communicate through local and/or remote processes such as according to a signal having one or more data packets (eg data from one component interacting with another component in a local system, distributed system, and/ or over a network such as the Internet with other systems via signal).
    [0020] Referring initially to Figure 1 and Figure 2, a portable computing device (PCD) is shown and is generally designated 100. As shown, PCD 100 may include a housing 102. Housing 102 may include a portion of upper housing 104 and a lower housing part 106. Figure 1 shows that the upper housing part 104 may include a screen 108. In a particular aspect, the screen 108 may be a touch-sensitive screen. The upper housing portion 104 may also include a trackball input device 110. Additionally, as illustrated in Figure 1, the upper housing portion 104 may include an on button 112 and an off button 114. As illustrated in Figure 1 , the upper housing portion 104 of the PCD 100 may include a plurality of indicator lights 116 and a speaker 118. Each indicator light 116 may be a light-emitting diode (LED).
    [0021] In a particular aspect, as described in Figure 2, the upper housing part 104 is movable with respect to the lower housing part 106. Specifically, the upper housing part 104 can be slidable with respect to the lower housing part 106 As illustrated in Figure 2, the lower housing portion 106 may include a multi-button keyboard 120. In a particular aspect, the multi-button keyboard 120 may be a standard QWERTY keyboard. The multi-button keyboard 120 may be revealed when the upper housing portion 104 is moved with respect to the lower housing portion 106. Figure 2 further illustrates that the PCD 100 may include a reset button 122 in the lower housing portion 106.
    [0022] Referring to Figure 3, an exemplary non-limiting aspect of a portable computing device (PCD) is shown and is generally designated 320. As shown, the PCD 100 includes a system-on-chip 322 that includes a multi-core CPU 324. The multi-core CPU 324 may include a zero core 325, a first core 326, and an N core 327.
    [0023] As illustrated in Figure 3, a display controller 328 and a touch screen controller 330 are coupled to the multi-core CPU 324. In turn, a touch screen 332 external to the system-on-chip 322 is coupled to the display controller 328 and touch screen controller 330.
    [0024] Figure 3 further indicates that a 334 video encoder, for example, a phase-altered line encoder (PAL), a memory sequential color encoder (SECAM), or a national television systems committee encoder ( NTSC), is coupled to multi-core CPU 324. Additionally, a video amplifier 336 is coupled to video encoder 334 and touch screen 332. In addition, a video port 338 is coupled to video amplifier 336. As depicted in Figure 3, a universal serial bus (USB) controller 340 is coupled to the multi-core CPU 324. In addition, a USB port 342 is coupled to the USB controller 340. A memory 344 and an identity module card. subscriber (SIM) 346 can also be coupled to the multi-core CPU 324. Additionally, as illustrated in Figure 3, a digital camera 348 can be coupled to the multi-core CPU 324. In an exemplary aspect, the digital camera 348 is a camera available charge-coupled sensor (CCD) or a metal oxide semiconductor camera (CMOS).
    [0025] As further illustrated in Figure 3, a stereo audio CODEC 350 can be coupled to the multi-core CPU 324. In addition, an audio amplifier 352 can be coupled to the stereo audio CODEC 350. In an exemplary aspect, a a first stereo speaker 354 and a second stereo speaker 356 are coupled to the audio amplifier 352. Figure 3 shows that a microphone amplifier 358 can also be coupled to the stereo audio CODEC 350. Additionally, a microphone 360 can be coupled to the microphone amplifier 358. In a particular aspect, a frequency modulation (FM) radio tuner 362 can be coupled to the stereo audio CODEC 350. In addition, an FM antenna 364 is coupled to the FM radio tuner 362. the 366 stereo headphones can be coupled to the 350 stereo audio CODEC.
    [0026] Figure 3 further indicates that a radio frequency (RF) transceiver 368 can be coupled to the multi-core CPU 324. An RF switch 370 can be coupled to the RF transceiver 368 and an RF antenna 372. As shown in Figure 3, a keyboard 374 can be coupled to the multi-core CPU 324. In addition, a mono headset with a microphone 376 can be coupled to the multi-core CPU 324. Additionally, a vibration device 378 can be coupled to the Multi-core CPU 324. Figure 3 also illustrates that a power supply 380 can be coupled to the system on chip 322. In one particular aspect, the power supply 380 is a direct current (DC) power supply that provides power. for the various components of the PCD 100 that require power. Additionally, and a particular aspect, the power supply is a rechargeable DC battery or a DC power supply that is derived from an alternating current (AC) to DC transformer that is connected to an AC power source.
    [0027] Figure 3 further indicates that the PCD 100 may also include a network card 388 that can be used to access a data network, for example, a local area network, a personal area network, or any other network. . The 388 network card can be a Bluetooth network card, a WiFi network card, a personal area network (PAN) card, a personal area network (PeANUT) ultra low energy technology network card, or any other network card well known in the art. Additionally, the 388 network card may be embedded in a chip, that is, the 388 network card may be a complete solution in a chip, and may not be a separate 388 network card.
    [0028] As depicted in Figure 3, the touch screen 332, the video port 338, the USB port 342, the camera 348, the first stereo speaker 354, the second stereo speaker 356, the microphone 360, the FM antenna 364, stereo phones 366, RF switch 370, RF antenna 372, keyboard 374, mono headset 376, vibrator 378, and power supply 380 are external to the 322 on-chip system.
    [0029] In a particular aspect, one or more method steps described herein may be stored in memory 344 as computer program instructions. These instructions can be executed by the multi-core CPU 324 in order to carry out the methods described here. Additionally, the multi-core CPU 324, memory 344, or any combination thereof can serve as a means to perform one or more of the method steps described herein in order to perform a plurality of tasks or strings. The multi-core CPU 324, memory 344 or any combination thereof can also serve as a means of performing one or more of the method steps described here in order to statically update a string priority quantization, a string quantum value, or a combination of them. Additionally, the multicore CPU 324, memory 344 or any combination thereof can serve as a means of performing one or more of the method steps described herein in order to dynamically update a string priority quantization, a string quantum value. , or a combination thereof. In addition, the multicore CPU 324, memory 344, or any combination thereof can serve as a means of assigning a priority to each of a plurality of strings.
    [0030] With reference to Figure 4, a processing system is shown and is generally designated 400. In a particular aspect, the processing system 400 may be incorporated into the PCD 100 described above in conjunction with Figure 3. As shown, the processing system 400 may include a multicore CPU 324 and a memory 344 connected to the multicore CPU 324. The multicore CPU 324 may include a zero core 325, a first core 326, and an N core 327. The zero core 325 may include a zero dynamic clock and voltage scaling algorithm (DCVS) 416 being executed. First core 326 may include a first DCVS algorithm 417 being executed. Additionally, the N core 327 may include an N DCVS 418 algorithm being executed. In a particular aspect, each DCVS algorithm 416, 417, 418 can run independently on a respective core 326, 327, 416.
    [0031] In addition, as illustrated, memory 344 may include an operating system 420 stored therein. Operating system 420 may include a scheduler 422 and scheduler 422 may include a first execution queue 424, a second execution queue 426, and an N execution queue 428. Memory 344 may also include a first application 430, a second application 432, an application N 434 stored in it.
    [0032] In a particular aspect, applications 430, 432, 434 may send one or more tasks 436 to operating system 420 to be processed on cores 325, 326, 327 within multi-core CPU 324. Tasks 436 may be processed, or performed, as single tasks, chains, or a combination of these. Additionally, scheduler 422 may schedule the tasks, strings, or a combination thereof for execution within multi-core CPU 324. Additionally, scheduler 422 may place the tasks, strings, or a combination thereof into execution queues 424,426,428. Cores 325, 326, 327 can retrieve tasks, strings, or a combination thereof from execution queues 424, 426, 428 as instructed, for example, by operating system 420 to process, or execute, those tasks and strings in the cores 325, 326, 327.
    [0033] In a particular aspect, the programmer 422, memory 344, cores 325, 326, 327, or any combination thereof may serve as a means to perform one or more of the method steps described herein in order to perform a plurality of tasks/strings 436. Scheduler 422, memory 344, cores 325, 326, 327, or any combination thereof may also serve as a means to perform one or more of the method steps described herein in order to statically update a string priority quantization, a string quantum value, or a combination thereof. In addition, programmer 422, memory 344, cores 325, 326, 327, or any combination thereof can serve as a means to perform one or more of the method steps described herein in order to dynamically update a priority quantization of string, a string quantum value, or a combination thereof. Additionally, scheduler 422, memory 344, cores 325, 326, 327, or any combination thereof may serve as a means of assigning a priority to each of a plurality of strings.
    [0034] In a particular aspect, string priorities can be reconciled, or otherwise handled by analyzing the various strings 436 and their dependencies and assigning a priority value based on the critical mode associated with processing each string 436. As the number of concurrent strings increases and the number of priorities increases, it becomes more complex to reconcile the 436 strings based on their respective priorities. As described here, each string can have a specified priority value, a quantized priority value, and a quantum value.
    [0035] The specified priority values can be expressed as relative values, for example, high, medium or low corresponding to buckets 504, 506 and 508 as illustrated in figure 2 and described in detail below. Quantum values can be expressed as time values, for example, milliseconds. For example, a particular string might have a quantum value of one millisecond (1 ms), five milliseconds (5 ms), ten milliseconds (10 ms), and so on.
    [0036] Based on the specified priority value, the quantized priority value and the quantum value of each string, the strings 436 can be processed in a way that allows the relatively more critical strings 436 to be processed without eliminating the strings 436 minus criticism. Additionally, in situations where multiple chains are running substantially simultaneously and have substantially the same critical level, i.e. priority, the chains can exchange with each other, for example, through the use of quantum values, in order to allow each proceed to process without deleting any string.
    [0037] Figure 5 illustrates a prioritization system that is generally referred to as 500. As illustrated, quantized prioritization system 500 may include a scheduler 422. Scheduler 422 may have access to a first chain bucket 504. scheduler 422 may have access to a second bucket of string 506. As shown, scheduler 422 may also have access to a bucket of string N 508. In a particular aspect, as illustrated, scheduler 422 may have access to three buckets of string 504, 506, 508 which correspond to three priority values of high, medium and low priority. However, it can be appreciated that the programmer 422 may have access to four buckets of string, five buckets of string, six buckets of string, etc. which correspond to other intermediate priority values (not shown).
    [0038] In a particular aspect, each bucket of chain 504 may receive a bucket priority value 510, 512, 514. Specifically, the first bucket of chain 504 may receive a first bucket priority value of 510. string 506 can receive a second bucket priority value 512. In addition, string bucket N 508 can receive a bucket priority value N 514.
    [0039] In one aspect, bucket priority values 510, 512, 514 may be relative to each other. For example, the first bucket priority value 510 might be a high bucket priority value. The second bucket priority value 512 can be an intermediate bucket priority value. Additionally, the third bucket priority value 514 can be a low bucket priority value. Strings, described below, can be placed in each bucket 504, 506, 508 based on a specified priority value associated with each string. Strings with similar specified priority values can be placed in the same bucket 504, 506, 508.
    [0040] Still referring to Figure 5, the first bucket 504 may include a first string 520 and a second string 522. The first string 520 may include a specified priority value 524, a quantized priority value 526, and a quantum value 528. A specified priority value 524 is a priority value specified by the string. The specified priority value is used to prioritize the execution of the strings. For example, a higher priority value can cause a particular chain to run before a chain having a lower priority value. A quantized priority value 526 may be a priority value determined at least partially based on string execution information. The quantum value 528 can be a slice of time a chain can allow to run before being impeded by another chain in the same bucket. As shown, the second string 522 may include a specified priority value 530, a quantized priority value 532, and a quantum value 534.
    [0041] As shown in Figure 5, the second bucket 506 may include a third string 540 and a fourth string 542. The third string 540 may include a specified priority value 544, a quantized priority value 546, and a quantum value 548 As illustrated, the fourth string 542 may include a specified priority value 550, a quantized priority value 552, and a quantum value 554.
    Bucket N 508 may include an (N-1) string 560 and an N string 562. The (N-1) string 560 may include a specified priority value 564, a quantized priority value 566, and a value quantum 568. As illustrated, the string N 562 can include a specified priority value 570, a quantized priority value 572, and a quantum value 574.
    [0043] In a particular aspect, strings 520, 522, 540, 542, 560, 562 can be moved by scheduler 422 between buckets 504, 506, 508 based on the runtime information associated with each string. For example, a quantized priority value 526 associated with the first string 520 may become less than the bucket priority value 510 associated with the first bucket 504. If the quantized priority value 526 of the first string 520 becomes less than the value of bucket priority 510 of the first bucket 504, the first string 520 can be moved by scheduler 422 from the first bucket 504 to the second bucket 506 or bucket N 508, depending on the quantized priority value 526 of the first string 520.
    [0044] As another example, the quantized priority value 546 associated with the third string 540 may become greater than the bucket priority value 512 associated with the second bucket 506. If the quantized priority value 546 of the third string 540 becomes greater than the bucket 512 priority value associated with the second bucket 506, the third string 540 may be moved by the scheduler 422 from the second bucket 506 to the first bucket 504.
    [0045] Figure 5 additionally shows a quantized priority value map 580 and a quantum value map 582 that are accessible to the scheduler 422. The scheduler 422 can map the quantized priority value 526, 532, 546, 552, 566, 572 associated with each string 520, 522, 540, 542, 560, 562 for the specified priority value 524, 530, 544, 550, 564, 570 of each string 520, 522, 540, 542, 560, 562 and store each one in the quantized priority value map 580 with an association to the appropriate string 520, 522, 540, 542, 560, 562. Additionally, the programmer 422 may map the quantum value 528, 534, 548, 554, 568, 574 associated with each string 520, 522, 540, 542, 560, 562 for the specified priority value 524, 530, 544, 550, 564, 570 of each string 520, 522, 540, 542, 560, 562 and stores each on the map of quantum value 582 with a suitable string association 520, 522, 540, 542, 560, 562. Quantized priority value map 580 lists all strings 436 c based on your quantized priority values regardless of your bucket priority assignments. Similarly, quantum value map 582 lists all 436 strings based on their quantum values independent of their bucket priority assignments.
    [0046] Prioritization system 500 allows the scheduler 422 to manage strings 436 within their assigned buckets 504, 506, 508 and to reassign strings 436 to other buckets 504, 506, and 508 as priorities may change or change during the uptime/runtime. This management of 436 chains within their respective designated buckets 504, 506 and 508 during runtime can be referred to as dynamic updating of chain priorities.
    [0047] Meanwhile, with the 580 quantized priority value map and the 582 quantum value map, the 422 programmer can also track and update the priorities between strings 436 independent of their individual bucket assignments and less frequently with respect to tracking of bucket designation. This tracking and updating of priorities between 436 chains based on maps 580 and 582 independent of bucket assignments and less frequently with respect to bucket assignment tracking is often referred to as static updating of chain priorities.
    [0048] Figure 6 illustrates a method of assigning a priority to each of the plurality of strings and is shown and generally designated as 600. Starting at block 602, a programmer 422 may receive a specified priority value for a string 602 Method 600 may proceed to block 606 and scheduler 422 may determine a quantized priority value for the string.
    [0049] Moving to block 608, programmer 422 can associate a quantized priority value with the specified priority value to the string. Additionally, at block 610, programmer 422 may associate a quantum value with the specified priority value and string. After that, method 600 can be terminated.
    [0050] During operation, the programmer 422 can use the quantized priority value, the quantized priority value, and the quantum value for each string to control the processing of each string. For example, a string having a higher specified priority value or quantized priority value can run before a string having a lower specified quantized priority value or priority value.
    [0051] If two strings have substantially the same specific priority values, or quantized priority values, and are located in the same bucket, the strings can be processed based on their associated quantum values. In such a case, if a particular string has a quantum value of five milliseconds (5 ms) and another string has a quantum value of one millisecond (1 ms). A string having a quantum value of five milliseconds may be allowed to run for five milliseconds, or until it is complete (whichever is less) and then the string having a quantum value of one millisecond will be allowed to run, or function. In particular, with round Robin programming, chain execution can continue to alternate between two chains until one or both chains complete their respective work.
    [0052] Referring to Fig. 7, a method for executing a plurality of strings is shown and is generally designated as 700. In a particular aspect, an operating system(os)/process programmer string 422 can be modified in order to quantize the string priority specified in a few discrete buckets 504, 506, 508. Each bucket can have a particular priority and all strings at a particular priority can be given the bucket's priority. Additionally, each of the strings in a particular bucket can be executed by the programmer 422 as if it had the same priority. However, each string in a particular bucket can also be assigned a programmer quantum value, that is, the maximum slice of time a string can run before being impeded by another string in the same bucket. Scheduler 422 can further quantize the priority of the strings in each bucket based on a scheduler quantum value assigned to each string.
    [0053] For example, programmer 422 can place each string into one of three buckets, for example, a high priority bucket, an intermediate priority bucket, and a low priority bucket. Then, the priority of each string within each bucket can be quantized to a programmer quantum value. During execution, chains within a particular bucket can run before chains in another bucket, for example, highest before middle and lowest, middle before lowest, etc. The strings within a particular bucket can be executed based on the programmer-specific quantum value of each string.
    [0054] Each string can be a part of a workload associated with a video app, an audio app, an email app, a wireless network app, a cellular network app, a service app a short message app (SMS), a communication app, a security app, a calendar app, an instant messaging app, a photo camera app, a global positioning system (GPS) app, a browser app , a notepad app, a clock app, a games app, a calculator app, a banking app, a password keeping app, a help app, an ecommerce app, a distribution app software, a search application, an options application, a setup application, a telephony application, a connection management application, any other application, or a combination of these.
    [0055] Beginning at block 704, when a string at rest 706 is ready to run, a scheduler 422 can map a specified priority value per string to a quantized priority value by creating three buckets with three different priorities. In a particular aspect, the quantized priority value can be determined based on the actual running time determined for a particular string. In one particular aspect, programmer 422 may statically map the specified priority value per string to the quantized priority value, such as quantized map 580 of Figure 5. In another aspect, programmer 422 may statically map the specified priority value per string to a quantum value, such as the quantum map 582 in Figure 5.
    [0056] In a particular aspect, a string at rest 706 can be a string that is not yet in the execution queue, a string that has just started running, or a combination of the two. At block 708, programmer 422 can add the string to a ready-to-run queue. Additionally, at block 710, scheduler 422 may update a string quantized priority value, a string quantum value, or a combination thereof. In a particular aspect, the programmer 422 may update the string quantized priority value, the string quantum value, or a combination thereof statically, as described below by using the static update method 710a of Fig. 8 or the update method dynamics 710b of figure 9.
    [0057] Moving to block 712, programmer 422 can select the next of the highest quantized priority value strings in the execution queue to be executed, that is, for execution on a processor. In one particular aspect, programmer 422 can select the next highest quantized priority value string in round Robin mode. Otherwise, programmer 422 can perform this selection in any other way well known in the art. At block 714, programmer 422 can map the specified priority value by string to the string quantum value, i.e., time slice. After that, the chain can run, or run, on a processor. The processor can be a single-core CPU, a multi-core CPU, multiple single-core CPUs, multiple multi-core CPUs, or a combination thereof.
    [0058] By moving to decision 718, scheduler 422 can determine whether the network associated with the chain being run 716 is complete. If the work has not been completed, method 700 can return to block 710 and method 700 can continue as described here. At decision 718, if the work is completed, method 700 can proceed to block 720 and the chain can enter a quiescent state. After that, method 700 may end.
    [0059] Referring to Fig. 8, a method 710a of statically updating a string priority quantization, a string quantum value, or a combination thereof is shown and generally designated 710a. Method 710a shown in Fig. 8 can be performed by a programmer 422 in order to update a string priority quantization, string quantum value, or a combination thereof.
    [0060] Beginning at block 802, programmer 422 may update an average runtime associated with a particular string. At block 804, scheduler 422 may statically map a specified string priority value to a quantized string priority value. In other words, a location in a quantized string priority map (MapQuantizePriority) 580 of Figure 5 can be set equal to a quantized priority value associated with a string.
    [0061] In a particular aspect, the map quantized priority value can be a static table that maps the chain priority into one of the quantized priorities. By moving to block 806, programmer 422 can statically map a specified string priority value to a string quantum value. In other words, a location in a string quantum value map (MapThreadQuantum value) 582 of Figure 5 can be set equal to a string quantum value associated with a string. The MapThreadQuantum value can be a static table that maps the string priority to a string quantum value, ie time slice. After that, method 710a can be terminated.
    [0062] Figure 9 describes a method 710b of dynamic update of string priority quantization, a string quantum value or a combination thereof is shown. The method is usually called 710b. Additionally, method 710b shown in Fig. 9 can be executed by a programmer 422 in order to update a string priority quantization, string quantum value, or a combination thereof.
    [0063] Beginning at block 902, programmer 422 may update the average runtime associated with a particular string. At block 904, programmer 422 may set a Quantum value(Thread) value equal to an AvgRuntime(Thread) value. The Quantum value(Thread) value can be a current quantum value associated with a string. Additionally, the AvgRunTime(Thread) value can be an average amount of time a thread runs between periods of inactivity.
    [0064] By moving to decision 906, programmer 422 can determine if a QuantizedPriority(Thread) value is less than a MaxPriority(Thread) value, where the QuantizedPriority(Thread) value is a current quantized priority value associated with a string and the MaxPriority(Thread) value is a maximum priority at which the string should run. If the QuantizedPriority(Thread) value is less than the MaxPriority(Thread) value, method 710b can proceed to decision 908 and programmer 422 can determine if the AvgRuntime(Thread) value is less than a MinAvgRuntime(Bucket) value, where the MinAvgRuntime(Bucket) value is a minimum average runtime that all strings in a particular bucket must maintain.
    [0065] If the AvgRuntime(Thread) value is less than the MinAvgRuntime(Bucket) value, the 710b method can proceed to block 910 and the 422 programmer can set the QuantizedPriority(Thread) value equal to a next plus quantized priority value high, that is, the chain is promoted to the next bucket in the bucket sequence with a higher priority than the current bucket's priority. After that, method 710b can return to decision 906 and method 710b can continue as described here. Returning to decision 908, if the AvgRuntime(Thread) value is not less, that is, greater than or equal to the MinAvgRuntime(Bucket) value, method 710b can proceed with decision 912. Additionally, returning to the decision 906, if QuantizedPriority(Thread) is not less, that is, greater than or equal to the MaxPriority(Thread) value, method 710b can also proceed to decision 912.
    [0066] In decision 912, programmer 422 can determine if the QuantizedPriority(Thread) value is greater than the MinPriority(Thread) value where the MinPriority(Thread) value is a minimum priority at which the string should run. If the QuantizedPriority(Thread) value is greater than the MinPriority(Thread) value, then method 710b can proceed to decision 914 and programmer 422 can determine if the AvgRuntime(Thread) value is greater than a MaxAvgRuntime(Bucket) value , where the MaxAvgRuntime(Bucket) value is a maximum average runtime that all chains in a particular, ie current, bucket should maintain.
    [0067] If the AvgRuntime(Thread) value is greater than the MaxAvgRuntime(Bucket) value, the 710b method can proceed to block 916 and the 422 programmer can set the QuantizedPriority(Thread) value equal to a next quantized priority value lower, that is, the chain is demoted to the next bucket in the bucket sequence with a lower priority than the current bucket's priority. After that, the method can return to decision 912 and method 710b can continue as described here. Returning to decision 914, if the AvgRuntime(Thread) value is not greater, that is, less than or equal to the MaxAvgRuntime(Bucket) value, method 710b can proceed to decision 1002 of Figure 10. Returning to decision 912 , if the QuantizedPriority(Thread) is not greater, that is, less than or equal to the MinPriority(Thread), method 710b can also proceed to decision 1002 of Figure 10.
    [0068] In decision 1002 of Figure 10, programmer 422 can determine if an AvgSchedTime(Bucket) value is greater than a MaxAvgSchedTime(Bucket) value where AvgSchedTime(Bucket) value is the average amount of time it takes for a string to start after being queued to execute when in a particular bucket and the MaxAvgSchedTime(Bucket) value can be a maximum average scheduling time that is desirable for a particular bucket. In a particular aspect, the placement of a string can be an initial placement or a replacement after the string has run and exhausted its quantum value.
    [0069] If the AvgSchedTime(Bucket) value is not greater than, that is, is less than or equal to the maxAvgSchedTime(Bucket) value, method 710b can be terminated. Otherwise, if the AvgSchedTime(Bucket) value is greater than the maxAvgSchedTime(Bucket) value, method 710b can proceed to decision 1004 and programming can determine if a LargestThreadQuantum value(Bucket) value is greater than a MinThreadQuantum value(Bucket) value ), where the LargestThreadQuantum value(Bucket) value is the largest quantum value for any string in a particular bucket and the MinThreadQuantum value(Bucket) value is the desired minimum string quantum value for any string in a particular bucket. If the LargestThreadQuantum value(Bucket) value is actually greater than the MinThreadQuantum value(Bucket) value, method 710b can proceed to block 1006.
    [0070] In block 1006, the programmer 422 can reduce a Quantum value(LargestThread) value by an integer, where the Quantum value(LargestThread) value is a higher string quantum value in a particular bucket. Additionally, at block 1006, programmer 422 can reduce the value of AvgSchedTime(Bucket) by an integer. After that, method 710b can return to decision 1002 and method 710b can continue as described here.
    [0071] Returning to decision 1004, if the LargestThreadQuantum value(Bucket) value is not greater than, that is, less than or equal to the MinThreadQuantum value(Bucket), method 710b can proceed to decision 1008. In decision 1008, method 710b can determine if the LowestMinThreadPriority(Bucket) value is less than a Priority(Bucket) value, where the LowestMinThreadPriority(Bucket) value is the lowest minimum priority for any string in a particular bucket and the Priority(Bucket) value is a priority of the particular bucket. If the LowestMinThreadPriority(Bucket) value is not less than, that is, greater than or equal to the Priority(Bucket) value, method 710b may terminate.
    [0072] Conversely, if the LowestMinThreadPriority(Bucket) value is less than the Priority(Bucket) value, method 710b can proceed to block 1010. In block 1010, programmer 422 can set a QuantizedPriority(LowestThread) value equal to a next lowest quantized priority value, where LowestThread is the string with the lowest minimum priority, that is, the string with the lowest minimum priority is demoted to the next bucket in the sequence of buckets with a priority lower than the priority of the current bucket. Additionally, in block 1010, programmer 422 can set the AvgSchedTime(Bucket) value equal to the maximum of zero or the AvgSchedTime(Bucket) value minus a Quantum value(LowestThread), where the Quantum value(LowestThread) value is the quantum value of the chain with the lowest minimum priority in the current bucket. After that, method 710b can return to decision 1002 and method 710b can continue as described here.
    [0073] It should be understood that the method steps described here do not necessarily need to be performed in the order as described. Additionally, words such as “after that”, “then”, “next”, etc. they should not limit the order of steps. These words are simply used to guide the reader through the description of the method steps. Also, the methods described here are described as executable on a portable computing device (PCD). The PCD can be a mobile phone device, a handheld digital assistant device, a smartbook computing device, a netbook computing device, a laptop computing device, a desktop computing device, or a combination thereof. Additionally, the method steps described herein can be performed on a single-core processor, a multi-core processor, multiple single-core processors, multiple multi-core processors, or any combination thereof.
    [0074] With the configuration described here, systems and methods can quantize the chain priority into a small number of programmable priorities and to the programmer's quantum value (slice of time) for the chain. Additionally, systems and methods can substantially eliminate the total depletion of a lower priority chain induced by a higher priority chain running continuously, when the chains are quantized at the same effective priority. Systems and methods can also substantially reduce the limit on the maximum amount of time that a lower priority chain is exhausted due to continuous execution of a higher priority chain when the chains are quantized at the same effective priority.
    [0075] In a particular aspect, systems and methods can substantially reduce the complexity of the search for chain priority by inducing conditions of competition and exhaustion, for example, due to a reduced number of chain priorities. In addition, the systems and methods described here can allow strings with higher specified priorities to get an increased percentage of processing time without exhausting other strings while the string is in the programmer's execution queue. The systems and methods here may additionally allow a specified chain priority to be changed to increase the chain's CPU utilization without changing the effective priority and as such may not result in undesirable, or otherwise unexpected, exhaustion of other chains and /or competition conditions.
    [0076] In a particular aspect, the system and methods presented here can substantially reduce chain exhaustion due to reducing the number of programmable priority levels. By quantizing the specified priority value into fewer priorities and time division of each chain, total exhaustion, for example, caused by the highest priority chain always running, can be substantially eliminated whenever chains of different specified priorities are mapped at the same quantized priority value. Additionally, by quantizing the specified priority value into fewer priorities and time division of each chain, the duration of exhaustion, for example, caused by a higher priority chain always running, can be substantially reduced in a maximum of time slices accumulated from all other chains mapped to the same quantized priority value and simultaneously scheduled to run. In another aspect, by quantizing the specified priority value into fewer priorities, the probability of exhaustion and/or competition conditions is substantially reduced, since the analysis necessary to ensure that such conditions do not exist is combinatorially dependent on the number of priorities involved.
    [0077] The system and methods described here can allow strings with higher specified priority to get more CPU time by mapping high priority strings to larger quantum values. In a particular aspect, the larger the string quantum value, the longer the string can run, or run, before being stopped. As such, the chain can potentially have a higher percentage of CPU utilization, lower priority chains can run as well. Additionally, by changing a specified priority value per chain so that the quantized priority value per chain remains the same, it does not effectively change the priorities of the chains and does not result in a fundamental increase in deadlocks and/or competitive conditions.
    [0078] In one or more exemplary aspects, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software, the functions can be stored or transmitted as one or more instructions or code in a computer program product such as a machine readable medium, i.e. a computer readable medium. Computer-readable media includes both computer storage media and communication media including any medium that facilitates the transfer of a computer program from one place to another. A storage media can be any available media that can be accessed by a computer. By way of example, and not limitation, such computer-readable media may comprise RAM, ROM, EEPROM, CD-ROM or other optical disk store, magnetic disk store or other magnetic storage device, or any other medium that may be used to carry or store the desired program code in the form of instructions or data structures that can be accessed by a computer. Also, any connection is properly called a computer-readable medium. For example, if the software is transmitted from a network site, server, or other remote source using coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared, radio and microwave, then coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio and microwave are included in the definition of medium. Disc(disk) and disc(disc), as used herein, include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and blu-ray disc where disc(disk) normally reproduce data magnetically , while discs (disc) reproduce data optically with lasers. Combinations of the above should also be included within the scope of computer readable media.
    [0079] Although the selected aspects have been illustrated and described in detail, it will be understood that various substitutions and changes can be made without departing from the spirit and scope of the present invention, as defined by the appended claims.
    权利要求:
    Claims (8)
    [0001]
    1. Method of performing a plurality of strings (520, 522, 540, 542, 560, 562) quantized into a plurality of buckets of discrete strings (504, 506, 508), each bucket of string including one or more of the plurality of strings, and each bucket having a designated bucket priority value (510, 512, 514), each string having an associated string specified priority (524, 530, 544,550, 564, 570), a string quantized priority value(526), and a string quantum value (528, 534, 548, 554, 568,574), comprising: if a first string that is at rest is ready to run: determining (602) the string quantized priority value for the first string based in an actual runtime associated with the first chain; assign the first chain to the chain bucket based on a specified chain priority value associated with the first chain; map (704) the specified chain priority value associated with the first chain ( 706) for the value of chain quantized priority associated with the first chain by assigning the first chain to a chain bucket having a bucket priority value; mapping a quantum value associated with the first chain to the specified chain priority value, the chain quantum value identifying a maximum amount of time the first chain is allowed to run before being impeded by a second chain; add (708) the first chain to a ready-to-run queue; select (712) a chain from a plurality of chains to run in an execution queue, where the selected chain is selected from a group of chains based on the chain having a higher quantized priority value and where if the strings of the plurality of strings in the same bucket have the same specified priority values or quantized priority value, the string is selected based on the string quantum values; run the selected string in a processor of a computing device; updating (710) the chain quantized priority value, the chain quantum value or a combination thereof associated with the selected chain, characterized in that updating a chain comprises changing the value of priority specified in chain such that the quantum value associated with the chain remains the same and updating comprises one of: a static update utilizing from a map and a dynamic update based on the bucket priority value; and increase the quantum value associated with the first string to extend the maximum amount of time the first string is allowed to run before being impeded by the second string.
    [0002]
    2. Method according to claim 1, characterized in that the chain quantized priority value comprises a priority value for the chain based on a real running time of the chain.
    [0003]
    3. Method according to claim 1, characterized in that it further comprises mapping a quantized priority value to a selected priority value.
    [0004]
    4. Method according to claim 1, characterized in that the chain quantized priority value, the chain quantum value, or a combination thereof is updated statically, dynamically or in a combination thereof.
    [0005]
    5. Method according to claim 1, characterized in that it further comprises: updating a quantized string priority value, a string quantum value, or a combination thereof for the selected string, if the string quantum value associated with the selected string is complete.
    [0006]
    6. Method according to claim 1, characterized in that it further comprises: updating a chain quantized priority value, a chain quantum value, or a combination thereof for the selected chain, if the work associated with the chain selected is complete.
    [0007]
    7. Device for executing a plurality of strings (520, 522, 540, 542, 560, 562) quantized into a plurality of buckets of discrete strings (504, 506, 508), each string bucket including one or more among the plurality of chains, and each bucket having a designated bucket priority value (510, 512, 514), each chain having a specified priority in associated chain (524, 530, 544, 550, 564, 570), a quantized priority value string (526) and a string quantum value (528, 534, 548, 554, 568, 574), comprising: means for determining the string quantized priority value for a first string based on an associated actual runtime to the first chain, the first chain being at rest; means to assign the first chain to the chain bucket based on a specified chain priority value associated with the first chain; means to map the specified chain priority value associated with the first string for a value of chain quantized priority associated with the first chain if the first chain is ready to run by assigning the first chain to a chain bucket having a bucket priority value; means to map a quantum value associated with the first chain into the priority value specified in chain, the chain quantum value identifying a maximum amount of time the first chain is allowed to run before being impeded by a second chain; means to add the first chain to a queue ready for execution; means to select a chain from among a plurality of strings to run in an execution queue, wherein the selected string is selected from a group of strings based on the string having a higher quantized priority value, and where the strings of the plurality of strings in the same bucket have the same specified priority values or quantized priority value, the string is selected based on the quantum values of chain; means for executing the selected string in a processor; means for updating the string quantized priority value, the string quantum value or a combination thereof associated with a selected string, characterized in that the means for updating a string comprise means for changing the specified priority value in chain such that the quantum value associated with the chain remains the same, the means for updating comprising one of: means for statically updating using a map and means for updating dynamically based on a bucket priority value; and means to increase the quantum value associated with the first string to extend the maximum amount of time the first string is allowed to run before being impeded by the second string.
    [0008]
    8. Computer readable memory characterized in that it contains recorded thereon the method as defined in any one of claims 1 to 6.
    类似技术:
    公开号 | 公开日 | 专利标题
    BR112012022431B1|2021-08-03|METHOD AND DEVICE TO RUN A PLURALITY OF QUANTIZED CHAINS IN A PLURALITY OF DISCRETE CHAIN BUCKS AND COMPUTER-READABLE MEMORY
    EP2513746B1|2018-07-04|System and method for controlling central processing unit power with guaranteed transient deadlines
    US9201693B2|2015-12-01|Quota-based resource management
    KR20170062493A|2017-06-07|Heterogeneous thread scheduling
    JP2017526996A|2017-09-14|System and method for managing processor device power consumption
    BR112012014308B1|2021-01-19|method for power control of central processing unit, wireless device and computer-readable memory
    BR112012014306B1|2020-09-24|METHOD FOR CONTROLLING POWER IN A CENTRAL UNIT FOR MULTIPLE NUCLEUS PROCESSING, WIRELESS DEVICE AND COMPUTER-READY MEMORY
    US20070038763A1|2007-02-15|Method of enabling a multitasking computing device to conserve resources
    US20110145624A1|2011-06-16|System and method for asynchronously and independently controlling core clocks in a multicore central processing unit
    KR101516859B1|2015-05-04|System and method for controlling central processing unit power with guaranteed steady state deadlines
    US20110145616A1|2011-06-16|System and method for controlling central processing unit power in a virtualized system
    JP5662478B2|2015-01-28|System and method for sampling data in a central processing unit
    JP2018533122A|2018-11-08|Efficient scheduling of multiversion tasks
    US20140237476A1|2014-08-21|Centralized task scheduling
    WO2007098424A2|2007-08-30|System and method for multi-processor application support
    CN107533479B|2021-05-25|Power aware scheduling and power manager
    KR101890046B1|2018-08-20|Concurrent network application scheduling for reduced power consumption
    US20110173463A1|2011-07-14|System and method of tuning a dynamic clock and voltage switching algorithm based on workload requests
    US20200379804A1|2020-12-03|Multi-level scheduling
    Jeong et al.2007|Transparent and selective real-time interrupt services for performance improvement
    同族专利:
    公开号 | 公开日
    CN103140831B|2016-08-10|
    CN103140831A|2013-06-05|
    JP2013522724A|2013-06-13|
    US8904399B2|2014-12-02|
    KR101522081B1|2015-05-20|
    EP2548120A1|2013-01-23|
    WO2011115732A1|2011-09-22|
    BR112012022431A2|2016-07-05|
    US20110225590A1|2011-09-15|
    JP5593404B2|2014-09-24|
    KR20130004502A|2013-01-10|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US5812844A|1995-12-07|1998-09-22|Microsoft Corporation|Method and system for scheduling the execution of threads using optional time-specific scheduling constraints|
    US5826081A|1996-05-06|1998-10-20|Sun Microsystems, Inc.|Real time thread dispatcher for multiprocessor applications|
    US6658447B2|1997-07-08|2003-12-02|Intel Corporation|Priority based simultaneous multi-threading|
    US6182120B1|1997-09-30|2001-01-30|International Business Machines Corporation|Method and system for scheduling queued messages based on queue delay and queue priority|
    US5987492A|1997-10-31|1999-11-16|Sun Microsystems, Inc.|Method and apparatus for processor sharing|
    CA2252238A1|1997-10-31|1999-04-30|Sun Microsystems, Inc.|Method and apparatus for sharing a time quantum|
    US7051330B1|2000-11-21|2006-05-23|Microsoft Corporation|Generic application server and method of operation therefor|
    JP3975703B2|2001-08-16|2007-09-12|日本電気株式会社|Preferential execution control method, apparatus and program for information processing system|
    US7080376B2|2001-09-21|2006-07-18|Intel Corporation|High performance synchronization of accesses by threads to shared resources|
    AT392662T|2002-01-30|2008-05-15|Real Entpr Solutions Dev Bv|METHOD AND PROGRAMS FOR ADJUSTING PRIORITY LEVELS IN A DATA PROCESSING SYSTEM WITH MULTIPROGRAMMING AND PRIORIZED QUEENS CREATIVE EDUCATION|
    US7080379B2|2002-06-20|2006-07-18|International Business Machines Corporation|Multiprocessor load balancing system for prioritizing threads and assigning threads into one of a plurality of run queues based on a priority band and a current load of the run queue|
    US7536689B2|2003-01-10|2009-05-19|Tricerat, Inc.|Method and system for optimizing thread scheduling using quality objectives|
    US8566828B2|2003-12-19|2013-10-22|Stmicroelectronics, Inc.|Accelerator for multi-processing system and method|
    US7458077B2|2004-03-31|2008-11-25|Intel Corporation|System and method for dynamically adjusting a thread scheduling quantum value|
    US7487503B2|2004-08-12|2009-02-03|International Business Machines Corporation|Scheduling threads in a multiprocessor computer|
    DE102004054571B4|2004-11-11|2007-01-25|Sysgo Ag|Method for distributing computing time in a computer system|
    US7904906B2|2004-11-23|2011-03-08|Stratus Technologies Bermuda Ltd.|Tracking modified pages on a computer system|
    US8255912B2|2005-04-13|2012-08-28|Qualcomm Incorporated|Techniques for setting events in a multi-threaded system|
    US7802256B2|2005-06-27|2010-09-21|Microsoft Corporation|Class scheduler for increasing the probability of processor access by time-sensitive processes|JP5376042B2|2010-03-18|2013-12-25|富士通株式会社|Multi-core processor system, thread switching control method, and thread switching control program|
    US20130060555A1|2011-06-10|2013-03-07|Qualcomm Incorporated|System and Apparatus Modeling Processor Workloads Using Virtual Pulse Chains|
    US9086883B2|2011-06-10|2015-07-21|Qualcomm Incorporated|System and apparatus for consolidated dynamic frequency/voltage control|
    CN102740256A|2012-05-31|2012-10-17|华为终端有限公司|Method for shielding short message and mobile terminal|
    US8963933B2|2012-07-23|2015-02-24|Advanced Micro Devices, Inc.|Method for urgency-based preemption of a process|
    US9274832B2|2013-02-07|2016-03-01|Htc Corporation|Method and electronic device for thread scheduling|
    CN103995742B|2014-05-20|2017-02-22|万向钱潮股份有限公司|Embedded type real-time scheduling control device and method based on MCU|
    CN104536345A|2014-12-17|2015-04-22|万向钱潮股份有限公司|Multitask control method based on vehicle electrical control system|
    CN105828308B|2015-10-20|2020-10-16|维沃移动通信有限公司|Method for limiting communication function of electronic equipment, electronic equipment and micro base station|
    US10134103B2|2015-10-23|2018-11-20|Qualcomm Incorporated|GPU operation algorithm selection based on command stream marker|
    CN105843687A|2016-03-31|2016-08-10|乐视控股（北京）有限公司|Method and device for quantifying task resource|
    US10146583B2|2016-08-11|2018-12-04|Samsung Electronics Co., Ltd.|System and method for dynamically managing compute and I/O resources in data processing systems|
    CN109766131A|2017-11-06|2019-05-17|上海宝信软件股份有限公司|The system and method for the intelligent automatic upgrading of software is realized based on multithreading|
    CN110502320B|2018-05-18|2022-03-04|杭州海康威视数字技术股份有限公司|Thread priority adjusting method and device, electronic equipment and storage medium|
    US10866834B2|2019-03-29|2020-12-15|Intel Corporation|Apparatus, method, and system for ensuring quality of service for multi-threading processor cores|
    法律状态:
    2019-01-08| B06F| Objections, documents and/or translations needed after an examination request according [chapter 6.6 patent gazette]|
    2019-09-17| B06U| Preliminary requirement: requests with searches performed by other patent offices: procedure suspended [chapter 6.21 patent gazette]|
    2021-02-09| B07A| Technical examination (opinion): publication of technical examination (opinion) [chapter 7.1 patent gazette]|
    2021-05-25| B09A| Decision: intention to grant [chapter 9.1 patent gazette]|
    2021-06-01| B350| Update of information on the portal [chapter 15.35 patent gazette]|
    2021-08-03| B16A| Patent or certificate of addition of invention granted|Free format text: PRAZO DE VALIDADE: 20 (VINTE) ANOS CONTADOS A PARTIR DE 23/02/2011, OBSERVADAS AS CONDICOES LEGAIS. PATENTE CONCEDIDA CONFORME ADI 5.529/DF, QUE DETERMINA A ALTERACAO DO PRAZO DE CONCESSAO. |
    优先权:
    申请号 | 申请日 | 专利标题
    US31408510P| true| 2010-03-15|2010-03-15|
    US61/314,085|2010-03-15|
    US12/964.342|2010-12-09|
    US12/964,342|US8904399B2|2010-03-15|2010-12-09|System and method of executing threads at a processor|
    PCT/US2011/025890|WO2011115732A1|2010-03-15|2011-02-23|System and method of executing threads at a processor|
    [返回顶部]